package com.gy.algorithm.carl.linklistexa;

/**
 * @BelongsProject: javabase
 * @BelongsPackage: com.gy.algorithm.carl
 * @Author: gy
 * @Date: 2024/10/22 11:30
 * @Description:
 */
public class RemoveNthFromEnd24 {

    public static void main(String[] args) {
//        ListNode head5 = new ListNode(5);
//        ListNode head4 = new ListNode(4, null);
//        ListNode head3 = new ListNode(3, head4);
        ListNode head2 = new ListNode(2, null);
        ListNode head1 = new ListNode(1, head2);

        ListNode listNode = removeNthFromEnd(head1,1);
        while (listNode != null) {
            System.out.println(listNode.val);
            listNode = listNode.next;
        }
    }

    // end
    public static ListNode removeNthFromEnd(ListNode head, int n) {
        //新建一个虚拟头节点指向head
        ListNode dummyNode = new ListNode(0);
        dummyNode.next = head;
        //快慢指针指向虚拟头节点
        ListNode fastIndex = dummyNode;
        ListNode slowIndex = dummyNode;

        // 只要快慢指针相差 n 个结点即可
        for (int i = 0; i <= n; i++) {
            if(fastIndex == null) return head.next;// 超出范围了 把头删了
            fastIndex = fastIndex.next;
        }

        while (fastIndex != null) {
            fastIndex = fastIndex.next;
            slowIndex = slowIndex.next;
        }

        // 此时 slowIndex 的位置就是待删除元素的前一个位置。
        // 具体情况可自己画一个链表长度为 3 的图来模拟代码来理解
        // 检查 slowIndex.next 是否为 null，以避免空指针异常
        if (slowIndex.next != null) {
            slowIndex.next = slowIndex.next.next;
        }
        return dummyNode.next;
    }


    // write
    public static ListNode removeNthFromEnd1(ListNode head, int n) {
        if(null == head || n < 0) return head;

        ListNode pre = head;
        ListNode cur = head;

        for (int i = 0; i < n; i++) {
            ListNode tmp = cur.next;
            if(tmp == null){
                break;
            }
            cur = tmp;
        }

        while (cur != null && cur.next != null){
            pre = pre.next;
            cur = cur.next;
        }

        pre.next = cur;

        return head;
    }


    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}
